"""
三数之和
"""
from typing import List
from collections import defaultdict
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        在给定的整数数组中，找到所有独特的三元组，使得这三个数字的和为零。

        参数:
        nums: List[int] -- 给定的整数数组

        返回值:
        List[List[int]] -- 所有和为零的独特三元组列表
        """
        # 排序输入的数组
        nums.sort()
        res = []  # 用于存储结果的列表

        # 遍历数组中的每个元素，跳过重复的元素
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # 设置左右指针
            l, r = i+1, len(nums)-1

            # 通过左右指针来寻找符合条件的三元组
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                # 如果和大于0，移动右指针
                if s > 0:
                    r -= 1
                # 如果和小于0，移动左指针
                elif s < 0:
                    l += 1
                # 如果和等于0，找到一个符合条件的三元组
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    # 移动左右指针，跳过相同的元素
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1
                    r -= 1

        return res


if __name__ == '__main__':
    s = Solution()
    print(s.threeSum([-1,0,1,2,-1,-4]))
